package com.leet.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MinHeightTree {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Queue<Integer> queue = new LinkedList<>();
        List<List<Integer>> sgm = new ArrayList<>();
        // 初始化map
        for(int i = 0 ;i < n; i++){
            sgm.add(new ArrayList<>());
        }
        List<Integer> ans = new ArrayList<>();
        if(n == 1){
            ans.add(0);
            return ans;
        }
        // 读取放入map
        int[] degree = new int[n];
        for(int[] edge:edges){
            degree[edge[0]]++;
            degree[edge[1]]++;
            sgm.get(edge[0]).add(edge[1]);
            sgm.get(edge[1]).add(edge[0]);
        }
        for(int i = 0; i < n; i++){
            if(degree[i]==1){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            ans = new ArrayList<>();
            for(int i = 0; i < size; i++){
                Integer head = queue.poll();
                ans.add(head);
                for(int neigh:sgm.get(head)){
                    degree[neigh]--;
                    if(degree[neigh] == 1) queue.offer(neigh);
                }
            }
        }
        return ans;
    }
}
